package bfs;

import java.util.*;

/**
 * WordLadder
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: https://leetcode-cn.com/problems/word-ladder/
 * @date 2021/6/6
 **/
public class WordLadder {

    public static void main(String[] args) {
        String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};
        List<String> wordList = Arrays.asList(words);
        Solution1 solution = new Solution1();
        System.out.println(solution.ladderLength("hit", "cog", wordList));
    }

    static class Solution {
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            // beginWord，endWord以及wordList中的每一个word的长度均相同
            int len = beginWord.length();

            // 进行预处理，如下的预处理非常巧妙
            HashMap<String, ArrayList<String>> allComboDict = new HashMap<>();

            wordList.forEach(
                    word -> {
                        for (int i = 0; i < len; i++) {
                            String newWord = word.substring(0, i) + '*' + word.substring(i + 1, len);
                            ArrayList<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());
                            transformations.add(word);
                            allComboDict.put(newWord, transformations);
                        }
                    });

            Queue<MyPair<String, Integer>> Q = new LinkedList<>();
            Q.add(new MyPair(beginWord, 1));

            HashMap<String, Boolean> visited = new HashMap<>();
            visited.put(beginWord, true);

            while (!Q.isEmpty()) {
                MyPair<String, Integer> node = Q.remove();
                String word = node.getKey();
                int level = node.getValue();

                for (int i = 0; i < len; i++) {
                    String newWord = word.substring(0, i) + '*' + word.substring(i + 1, len);
                    for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
                        if (adjacentWord.equals(endWord)) {
                            return level + 1;
                        }
                        if (!visited.containsKey(adjacentWord)) {
                            visited.put(adjacentWord, true);
                            Q.add(new MyPair(adjacentWord, level + 1));
                        }
                    }
                }
            }
            return 0;
        }

        static class MyPair<K, V> {
            K key;
            V value;

            public MyPair(K key, V value) {
                this.key = key;
                this.value = value;
            }

            public K getKey() {
                return key;
            }

            public void setKey(K key) {
                this.key = key;
            }

            public V getValue() {
                return value;
            }

            public void setValue(V value) {
                this.value = value;
            }
        }
    }

    static class Solution1 {

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            int len = beginWord.length();

            Map<String, List<String>> map = new LinkedHashMap<>();

            wordList.forEach(word -> conversion(word, map));

            Queue<MyPair<String, Integer>> queue = new LinkedList<>();
            Set<String> visited = new HashSet<>();
            queue.add(new MyPair<>(beginWord, 1));
            visited.add(beginWord);

            while (!queue.isEmpty()) {
                MyPair<String, Integer> node = queue.remove();
                String word = node.getKey();
                int level = node.getValue();

                for (int i = 0; i < word.length(); i++) {
                    String newWord = word.substring(0, i) + "*" + word.substring(i + 1, len);
                    List<String> relatedWords = map.getOrDefault(newWord, new ArrayList<>());
                    for (String nextWord : relatedWords) {
                        if (nextWord.equals(endWord)) {
                            return level + 1;
                        }
                        if (!visited.contains(nextWord)) {
                            queue.add(new MyPair<>(nextWord, level + 1));
                            visited.add(nextWord);
                        }
                    }
                }
            }
            return 0;
        }

        public void conversion(String originWord, Map<String, List<String>> map) {
            int len = originWord.length();
            for (int i = 0; i < len; i++) {
                String newWord = originWord.substring(0, i) + "*" + originWord.substring(i + 1, len);
                List<String> relatedWords = map.getOrDefault(newWord, new ArrayList<>());
                relatedWords.add(originWord);
                map.put(newWord, relatedWords);
            }
        }

        class MyPair<K, V> {
            K key;
            V value;

            public MyPair(K key, V value) {
                this.key = key;
                this.value = value;
            }

            public K getKey() {
                return key;
            }

            public void setKey(K key) {
                this.key = key;
            }

            public V getValue() {
                return value;
            }

            public void setValue(V value) {
                this.value = value;
            }
        }
    }
}
